package com.lw.leetcode.arr.b;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 915. 分割数组
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/5 17:28
 */
public class PartitionDisjoint {

    public static void main(String[] args) {
        PartitionDisjoint test = new PartitionDisjoint();

        // 4
        int[] arr = {1,1,1,0,6,12};

        // 3
//        int[] arr = {5,0,3,8,6};

        // 5
//        int[] arr = {55,59,38,44,54,97,60,60,71,82};

        // 1
//        int[] arr = {1,1};

//        int i = test.partitionDisjoint2(arr);
//        System.out.println(i);

        int ki = test.partitionDisjoint(arr);
        System.out.println(ki);
    }



    public int partitionDisjoint(int[] nums) {
        int length = nums.length;
        int[] arr2 = new int[length];
        arr2[length - 1] = nums[length - 1];
        for (int i = length - 2; i >= 0; i--) {
            arr2[i] = Math.min(arr2[i + 1], nums[i ]);
        }
        int item = 0;
        for (int i = 1; i < length; i++) {
            item = Math.max(item , nums[i - 1]);
            if (arr2[i] >= item) {
                return i;
            }
        }
        return -1;
    }

    public int partitionDisjoint2(int[] nums) {
        int length = nums.length;
        int[] ints = Arrays.copyOf(nums, length);
        Arrays.sort(nums);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            map.put(nums[i], i);
        }
        int l = length;
        int max = Integer.MAX_VALUE;
        for (int i = length - 1; i > 0; i--) {
            int index = map.get(ints[i]);
            map.put(ints[i], index - 1);
            max = Math.min(max, index);
            if (max == i) {
                l = max;
            }
        }
        return l;
    }

}
